﻿// 0829train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 一个文件目录的数据格式为：
 目录id，本目录中文件大小，(子目录id列表）
 其中目录id全局唯一，取值范围[1, 200]
 本目录中文件大小范围[1, 1000]，子目录id列表个数[0,10]

例如 : 1 20 (2,3)表示目录1中文件总大小是20，有两个子目录，id分别是2和3
现在输入一个文件系统中所有目录信息，以及待查询的目录 id
返回这个目录和及该目录所有子目录的大小之和

输入描述
第一行为两个数字M，N，分别表示目录的个数和待查询的目录id,
1 ≤ M ≤ 100
1 ≤ N ≤ 200
接下来M行，每行为1个目录的数据：
目录id本目录中文件大小 (子目录id列表)
子目录列表中的子目录id以逗号分隔

输出描述
待查询目录以及其子目录之和

示例1
3 1
3 15 ()
1 20 (2)
2 10 (3)
输出
45

目录1大小为20，包含一个子目录2(大小为10)，子目录2包含1个子目录3(大小为15)，总的大小为20+10+15=45

哈希表（index value）vector<int,set<int>> bfs塞进查询节点
*/

class Solution01
{
public:
    void initGrid(vector<string>& origin_vec)
    {
        vector<vector<string>>grid0;

        for (auto&oh_str:origin_vec)
        {
            vector<string>min_grid;
            stringstream oh_sstream(oh_str);
            string token;
            while (oh_sstream>>token)
            {
                min_grid.push_back(token);
            }
            grid0.push_back(min_grid);
        }

        for (auto&min_grid:grid0)
        {
            for (int i=0; i<min_grid.size(); i++)
            {
                int index = stoi(min_grid[0]);
                int val = stoi(min_grid[1]);

                //更新val_map
                val_map[index] = val;

                string child_str = min_grid[2];
                unordered_set<int>child_set;
                if (child_str=="()")
                {
                    //没有child_set
                    grid_map[index] = child_set;
                    continue;
                }

                child_str = child_str.substr(1, child_str.size() - 2);

                stringstream oh_sstream(child_str);
                string token;
                while (getline(oh_sstream, token, ','))
                {
                    child_set.insert(stoi(token));
                }
                //更新grid_map
                grid_map[index] = child_set;
            }

        }

        //initGrid
    }

    Solution01(vector<string>&origin_vec, int search_node)
    {
        initGrid(origin_vec);

        deque<int>bfs_queue;
        bfs_queue.push_back(search_node);

        int result = 0;
        while (!bfs_queue.empty())
        {
            int top_node = bfs_queue.front();
            bfs_queue.pop_front();
            result += val_map.at(top_node);

            unordered_set<int>child_set = grid_map.at(top_node);

            for (auto&child_node:child_set)
            {
                bfs_queue.push_back(child_node);
            }

            //while (!bfs_queue.empty())
        }

        cout << result;
        //Solution01
    }
private:
    unordered_map<int, int>val_map;
    unordered_map<int, unordered_set<int>>grid_map;
};

/*
只有一个boss，其有若干一级分销，一级分销又有若干二级分销，每个分销只有唯一的上级分销
规定，每个月，下级分销需要将自己的总收入(自己的+下级上交的)
每满100元上交15元给自己的上级
现给出一组分销的关系，和每个分销的收入，请找出boss并计算出这个boss的收入

比如:
收入100元，上交15元;
收入199元（99元不够100），上交15元，
收入200元，上交30元
输入：
分销关系和收入:[[分销id 上级分销的Id 收入]，[分销id 上级分销的id 收入]，[分销id 上级分销的id 收入]]
分销ID范围0..65535
收入范围0..65535，单位元
提示：输入的数据只存在1个boss，不存在环路
输出：[boss的ID，总收入]


输入描述
第1行输入关系的总数量N
第2行开始，输入关系信息，格式：分销ID 上级分销ID 收入
比如:
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

输出描述
输出：boss的ID 总收入
比如：
0 120

示例
输入
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

输出
0 120
 */
class Solution02
{
public:
    void initMap(vector<string>& origin_vec)
    {
        vector<vector<int>>grid0;

        for (auto&oh_str:origin_vec)
        {
            vector<int>min_grid;
            string token;
            stringstream oh_sstream(oh_str);
            while (oh_sstream>>token)
            {
                min_grid.push_back(stoi(token));
            }
            grid0.push_back(min_grid);
        }

        for (auto&min_grid:grid0)
        {
            int index = min_grid[0];
            int val = min_grid[2];

            val_map[index] = val;

            int root = min_grid[1];
            //更新root,child关系
            linked_map[root].insert(index);
        }

        //更新indegree
        for (auto&root:linked_map)
        {
            indegree_map[root.first] += 0;
	        for (auto&child:root.second)
	        {
                indegree_map[child] += 1;
	        }
        }
        //initLinkedMap
    }


    int computedVal(int num)
    {
        return (num / 100) * 15;
    }

    Solution02(vector<string>&origin_vec)
    {
        initMap(origin_vec);

        deque<int>bfs_queue;

        for (auto&node: indegree_map)
        {
	        if (node.second==0)
	        {
                bfs_queue.push_back(node.first);
                root = node.first;
	        }
        }

        vector<vector<int>>layer_vec;

        int layer = 0;
        while (!bfs_queue.empty())
        {
            layer += 1;
            int q_size = bfs_queue.size();
            vector<int>layer_mini;
            for (int i=0; i<q_size; i++)
            {
                int top_node = bfs_queue.front();
                bfs_queue.pop_front();

                layer_mini.push_back(top_node);

                if (linked_map.count(top_node) == 0)
                {
                    //不存在子数组
                    continue;
                }
                //拿出子节点
                unordered_set<int>child_set = linked_map.at(top_node);

                //更新indegree
                for (auto& node : child_set)
                {
                    indegree_map[node] -= 1;
                }

                //indegree减到0，并且是root才能进bfs
                for (auto& node : child_set)
                {
                    if (indegree_map.at(node) == 0)
                    {
                        bfs_queue.push_back(node);
                    }
                }

            }

            layer_vec.push_back(layer_mini);
            //while (!bfs_queue.empty())
        }

        for (int i = layer_vec.size() - 2; i >= 0; i--)
        {
            vector<int>layer_mini = layer_vec[i];
            for (auto& curr_node :layer_mini)
            {
                if (linked_map.count(curr_node)==0 || linked_map.at(curr_node).empty())
                {
                    continue;
                }
                unordered_set<int>child_set = linked_map.at(curr_node);

                int curr_sum = 0;
                for (auto&child:child_set)
                {
                    curr_sum += computedVal(val_map[child]);
                }
                val_map[curr_node] += curr_sum;
            }
        }

        cout << root << ' ' << val_map[root];
        //Solution02
    }
private:
    int root = -1;
    unordered_map<int, int>indegree_map;
    unordered_map<int, int>val_map;
    unordered_map<int, unordered_set<int>>linked_map;
};

class Solution21
{
public:
    void initMap(vector<string>& origin_vec)
    {
        //indegree grid0[0]->grid0[1]

        for (auto&oh_str:origin_vec)
        {
            vector<int>min_grid0;
            string token;
            stringstream oh_sstream(oh_str);
            while (oh_sstream>>token)
            {
                min_grid0.push_back(stoi(token));
            }
            //更新linked_map
            //每个分销只有唯一的上级分销
            int start = min_grid0[0];
            int arrive = min_grid0[1];
            linked_map[start] = arrive;

            //每个节点都要进入度表
            indegree_map[start] += 0;
            indegree_map[arrive] += 1;

            //更新val_map
            val_map[start] = min_grid0[2];
        }

    }

    void updateUpperNode(int node)
    {
        //说明没有upper节点
        if (linked_map.count(node) == 0) return;

        int upper = linked_map.at(node);
        val_map[upper] += (val_map[node] / 100) * 15;

        //updateUpperNode
    }

    Solution21(vector<string>&origin_vec)
    {
        //linked_map indegree_map bfs_queue
        initMap(origin_vec);

        //入度为0，进bfs_queue
        deque<int>bfs_queue;
        for (auto&node:indegree_map)
        {
	        if (node.second==0)
	        {
                bfs_queue.push_back(node.first);
	        }
        }

        //更新上级节点val
        while (!bfs_queue.empty())
        {
            int q_size = bfs_queue.size();

            for (int i=0; i<q_size; i++)
            {
                int top_node = bfs_queue.front();
                bfs_queue.pop_front();

                if (linked_map.count(top_node)==0)
                {
	                //说明没有上级节点
                    root = top_node;
                }
                else
                {
                    updateUpperNode(top_node);
                    int upper = linked_map.at(top_node);
                    indegree_map[upper] -= 1;
                    if (indegree_map[upper]==0)
                    {
                        bfs_queue.push_back(upper);
                    }

                }
            }

            if (root!=-1)
            {
                //找到顶层节点break
                break;
            }


        }

        cout << root << ' ' << val_map[root];
	    //Solution21
    }
private:
    int root = -1;
    unordered_map<int, int>val_map;
    unordered_map<int, int>linked_map;
    unordered_map<int, int>indegree_map;
};

int main()
{
	{
/*
5
1 0 100
2 0 199
3 0 200
4 0 200
5 0 200

*/
        int v_size;
        string input;
        getline(cin, input);
        v_size = stoi(input);

        vector<string>origin_vec;

        while (getline(cin,input))
        {
            if (input.empty())break;
            origin_vec.push_back(input);
        }

        Solution21 solu(origin_vec);

        return 0;
	}
/*
3 1
3 15 ()
1 20 (2)
2 10 (3)
*/
    int v_size, search_node;
    //search_node = 1;
    cin >> v_size >> search_node;
    cin.ignore();

    vector<string>origin_v(v_size);
    for (int i=0 ;i<v_size; i++)
    {
        string input;
        getline(cin, input);
        origin_v[i] = input;
    }
    //vector<string>origin_v = {"3 15 ()","1 20 (2)","2 10 (3)"};

    Solution01(origin_v, search_node);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
